import heapq


class Solution(object):
    def constrainedSubsetSum(self, nums, k):
        st = []
        max_val = -float('inf')
        for index, num in enumerate(nums):
            while st and st[0][1] < index - k:
                heapq.heappop(st)
            if not st:
                heapq.heappush(st, [-num, index])
                max_val = max(max_val, num)
            else:
                val, _ = st[0]
                if val < 0:
                    num -= val
                max_val = max(max_val, num)
                heapq.heappush(st, [-num, index])
        return max_val

data = Solution()
nums = [10, 2, -10, 5, 20]
k = 2
print(data.constrainedSubsetSum(nums, k))
